import random
import time

# Implementation of binary search algorithm !

# Naive search: scan entire list and ask if its equal to the target
# if yes, return the index
# if no, then return -1
def naive_search(l, target):
    for i in range(len(l)):
        if l[i] == target:
            return i
    return -1

# First version of the binary search algorithm with recursion
# binary search uses divide and conquer !
# we will leverage the fact that our list is SORTED
def binary_search(l, target, low = None, high = None):
    # low and high are index
    if low is None:
        low = 0
    if high is None:
        high = len(l) - 1

    if high <= low:
        return -1
    midpoint = (low + high) // 2 # 2

    if l[midpoint] == target:
        return midpoint
    elif target < l[midpoint]:
        return binary_search(l, target, low, midpoint-1)
    else:
        # target > l[midpoint]
        return binary_search(l, target, midpoint+1, high)
    
# Second version of binary search algorithm with a while loop
def binary_search_iterative(l, target):
    # low and high are index
    low = 0
    high = len(l) - 1

    # adding a stepper to know in how many step, it is achieved
    # stepper = 0

    while low <= high:
        midpoint = (low + high) // 2
        if l[midpoint] == target:
            return midpoint
        elif target < l[midpoint]:
            high = midpoint - 1
        else:
            low = midpoint + 1
        # stepper += 1
    return -1

if __name__ =='__main__':
    # l = [1, 3, 5, 10, 12]
    # target = 10
    # print(naive_search(l, target))
    # print(binary_search(l, target))

    length = 50000
    # build a sorted list of length 10000
    sorted_list = set()
    while len(sorted_list) < length:
        sorted_list.add(random.randint(-3*length, 3*length))

    sorted_list = sorted(list(sorted_list))

    start = time.time()
    for target in sorted_list:
        naive_search(sorted_list, target)
    end = time.time()
    print("Naive search time:", (end - start)/length, "seconds")

    start = time.time()
    for target in sorted_list:
        binary_search(sorted_list, target)
    end = time.time()
    print("Binary search time:", (end - start)/length, "seconds")